package month1;

import java.util.Arrays;

public class MergeKSortedLists23_04 {
    public static void main(String[] args) {
        System.out.println(mergeKLists(new ListNode[]{new ListNode(new int[]{1, 2, 3, 5, 7}), new ListNode(new int[]{1, 2, 4, 8, 9})}));
    }

    /**
     * 递归吧
     * @param lists
     * @return
     */
    static ListNode mergeKLists(ListNode[] lists) {
        int n = lists.length;
        if (n == 1) {
            return lists[0];
        }
        if (n == 0) {
            return null;
        }
        return merge(mergeKLists(Arrays.copyOfRange(lists, 0, n / 2)), mergeKLists(Arrays.copyOfRange(lists, n / 2, n)));
    }

    static ListNode merge(ListNode l, ListNode r) {
        ListNode dummy = new ListNode();
        ListNode tmp = dummy;
        while (l != null || r != null) {
            int l1 = l == null ? Integer.MAX_VALUE : l.val, l2 = r == null ? Integer.MAX_VALUE : r.val;
            if (l1 < l2) {
                tmp.next = new ListNode(l1);
                l = l.next;
            } else {
                tmp.next = new ListNode(l2);
                r = r.next;
            }
            tmp = tmp.next;
        }
        return dummy.next;
    }
}
